package huffmanTree;


import com.cn.stepLock.lambda.LambdaUtil;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import com.google.common.collect.ImmutableList;
import io.netty.buffer.ByteBuf;
import io.netty.buffer.Unpooled;

import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Collectors;

import static com.cn.stepLock.lambda.LambdaUtil.*;
import static huffmanTree.ByteUtil.*;
import static huffmanTree.Utils.throwFunctionSupportException;

/**
 * @author Aaron
 * @desc
 * @createTime 2021/12/10 21:26
 * @since
 */
public abstract class AbstractHuffmanTree<T> implements HuffmanTree<T> {

    protected HuffmanNode<T> root;

    protected BiMap<T,String> compressMappingResult;

    protected Map<T,Long> valueFrequency;

    protected List<T> valueList;

    protected PriorityQueue<HuffmanNode<T>> huffmanTrees;

    protected byte[] compressResult;

    protected ByteBuf compressByteBuf;

    protected int bitIndex;

    protected int lastBitIndex;

    public AbstractHuffmanTree() {
        throwFunctionSupportException();
        this.compressMappingResult = HashBiMap.create();
        this.valueFrequency = new HashMap<>();
        this.valueList = new ArrayList<>();
        this.huffmanTrees = new PriorityQueue<>();
    }

    public AbstractHuffmanTree(List<T> valueList) {
        this.compressMappingResult = HashBiMap.create();
        this.valueFrequency = new HashMap<>();
        this.valueList = valueList;
        this.huffmanTrees = new PriorityQueue<>();
        buildTree();
    }

    public AbstractHuffmanTree(T value) {
        this.compressMappingResult = HashBiMap.create();
        this.valueFrequency = new HashMap<>();
        this.valueList =  new ArrayList<>();
        this.valueList.add(value);
        this.huffmanTrees = new PriorityQueue<>();
        buildTree();
    }

    @Override
    public Map<T,String> getCompressMappingResult(){
        return compressMappingResult;
    }

    public String getCompressedValue(){
        return valueList.stream().map(x -> compressMappingResult.get(x)).collect(Collectors.joining(""));
    }

    public void buildCompressResult(){
        this.compressResult = doBuildCompressResult();
        this.lastBitIndex = calculateLastBitIndex();
        this.compressByteBuf  = Unpooled.copiedBuffer(compressResult);
    }

    protected byte[] doBuildCompressResult() {
        byte[] compressResult =  new byte[calculateCompressResultLength()];
        StringBuffer byteCode = new StringBuffer();
        int i=0;
        for (int j = 0; j < valueList.size(); j++) {
            T t = valueList.get(j);
            byteCode  = byteCode.append(compressMappingResult.get(t));
            if (j==valueList.size()-1){
                byte[] byteByString = ByteUtil.getByteByString(byteCode.toString());
                for (byte b : byteByString) {
                        compressResult[i]=b;
                    i++;
                }
                break;
            }
            if (byteCode.length()<8){
                continue;
            }
            Integer integer = Integer.parseInt(byteCode.substring(0, 8), 2);
            byteCode = byteCode.delete(0,8);
            compressResult[i]=integer.byteValue();
            i++;
        }
        return compressResult;
    }

    @Override
    public int getLastBitIndex() {
        return lastBitIndex;
    }

    protected int calculateLastBitIndex(){
        return calculateLastBitIndex((int) calculateCompressCodeLength());
    }

    protected int calculateLastBitIndex(int length){
        int byteRemainder= getByteRemainder(length);
        return byteRemainder==0?7:byteRemainder-1;
    }

    protected int calculateCompressResultLength(long count) {
        int compressResultLength = (count & 7)>0?1:0;
        compressResultLength = compressResultLength+(int) (count>>3);
        return compressResultLength;
    }

    @Override
    public int calculateCompressResultLength() {
        return calculateCompressResultLength(calculateCompressCodeLength());
    }

    private long calculateCompressCodeLength() {
        return valueFrequency.keySet().stream().mapToLong(x -> valueFrequency.get(x) * compressMappingResult.get(x).length()).sum();
    }

    @Override
    public byte[] getCompressResult(){
        return compressResult;
    }
//11011111101101111011
    @Override
    public HuffmanTree<T> buildTree(){
        calculateValueFrequency();
        buildAllLeaf();
        buildAllNode();
        buildCompressMappingResult(root,new StringBuffer(), compressMappingResult);
        buildCompressResult();
        postHandleBuildTree();
        return this;
    }

    protected void postHandleBuildTree(){
        this.valueList=new ArrayList<>();
    }

    @Override
    public Map<T, Long> getValueFrequency() {
        return valueFrequency;
    }

    @Override
    public Iterator<T> iterator() {
        return new Itr(compressByteBuf);
    }

    @Override
    public Iterator<T> testIterator(ByteBuf byteBuf) {
        return new Itr(byteBuf);
    }

    public CompressValueItr compressValueIterator() {
        return new CompressValueItr(compressByteBuf);
    }

    public void resetIterator(){
        this.bitIndex=0;
        this.compressByteBuf.readerIndex(0);
    }

    private class Itr implements Iterator<T> {
//        int cursor;       // index of next element to return
//        int lastRet = -1; // index of last element returned; -1 if no such
        private int bitIndex=0;
        private int readIndex=0;
        private ByteBuf compressByteBuf;

        public Itr(ByteBuf compressByteBuf) {
            this.compressByteBuf = compressByteBuf.copy();
        }

        public boolean hasNext() {
            if (!compressByteBuf.isReadable()){
                return false;
            }
            if (compressByteBuf.readerIndex()==compressByteBuf.capacity()-1 && bitIndex>lastBitIndex){
                return false;
            }
            return true;
        }

        @SuppressWarnings("unchecked")
        public T next() {
            ifThrow(!hasNext(),()->new ConcurrentModificationException());
            if (root instanceof HuffmanLeaf){
                bitIndex = getByteRemainder(bitIndex+1);
                if (compressByteBuf.isReadable()){
                    compressByteBuf.readByte();
                }
                if (bitIndex>0){
                    compressByteBuf.readerIndex(compressByteBuf.readerIndex()-1);
                }
                return ((HuffmanLeaf<T>) root).value;
            }
            return (T)(resolveHuffmanLeaf(new ResolveHuffmanLeaf(root, readNextByte(), bitIndex)).value);
        }

        private class ResolveHuffmanLeaf<T>{
           HuffmanNode<T> huffmanNode;
           byte readByte;
            /**
             * 下一个需要读但是还没读的bitIndex
             */
           int nowBitIndex;

           boolean lastBit;
            private ResolveHuffmanLeaf(HuffmanNode<T> huffmanNode, byte readByte, int nowBitIndex) {
                this.huffmanNode = huffmanNode;
                this.readByte = readByte;
                this.nowBitIndex = nowBitIndex;
            }
        }

        private byte readNextByte(){
            return compressByteBuf.readByte();
        }

        private HuffmanLeaf<T> resolveHuffmanLeaf(ResolveHuffmanLeaf<T> resolveHuffmanLeaf){
            if (resolveHuffmanLeaf.huffmanNode instanceof HuffmanLeaf){
                /**
                 * 如果不是这个byte的最后一位则ByteBuf的readIndex回退一位
                 */

                bitIndex = resolveHuffmanLeaf.nowBitIndex;
                /**
                 * 如果到了最后一个
                 */
                if (!compressByteBuf.isReadable() && (resolveHuffmanLeaf.lastBit || bitIndex>lastBitIndex)){

                }else {
                    compressByteBuf.readerIndex(compressByteBuf.readerIndex() - 1);
                }
                return (HuffmanLeaf)resolveHuffmanLeaf.huffmanNode;
            }
            if (isTrueAtBitIndex(resolveHuffmanLeaf.readByte,resolveHuffmanLeaf.nowBitIndex)){
                resolveHuffmanLeaf.huffmanNode = resolveHuffmanLeaf.huffmanNode.right;
            }else {
                resolveHuffmanLeaf.huffmanNode = resolveHuffmanLeaf.huffmanNode.left;
            }
            resolveHuffmanLeaf.nowBitIndex = getByteRemainder(resolveHuffmanLeaf.nowBitIndex+1);
            if (resolveHuffmanLeaf.nowBitIndex==0){
                if (compressByteBuf.isReadable()) {
                    resolveHuffmanLeaf.readByte = readNextByte();
                }else {
                    resolveHuffmanLeaf.lastBit = true;
                }
            }
            return resolveHuffmanLeaf(resolveHuffmanLeaf);
        }

        private byte readByte() {
            byte readByte = compressByteBuf.readByte();
            if (bitIndex>0){
                if (hasNext()){
                    readByte = combineBytes(readByte,compressByteBuf.readByte(),bitIndex);
                    /**
                     * 指针回退一位防止下次漏掉拼接的数据
                     */
                    compressByteBuf.readerIndex(compressByteBuf.readerIndex()-1);
                }else {
                    readByte = splitByte(readByte,bitIndex,lastBitIndex);
                    bitIndex = lastBitIndex;
                }
            }
            return readByte;
        }

//        public void remove() {
//            if (lastRet < 0)
//                throw new IllegalStateException();
//            checkForComodification();
//
//            try {
//                ArrayList.this.remove(lastRet);
//                cursor = lastRet;
//                lastRet = -1;
//                expectedModCount = modCount;
//            } catch (IndexOutOfBoundsException ex) {
//                throw new ConcurrentModificationException();
//            }
//        }


        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super T> consumer) {
            Objects.requireNonNull(consumer);
            if (!hasNext()){
                return;
            }
            consumer.accept(next());
        }
    }

    private class CompressValueItr implements Iterator<StringBuffer> {
        //        int cursor;       // index of next element to return
//        int lastRet = -1; // index of last element returned; -1 if no such
        private int bitIndex=0;
        private int readIndex=0;
        private ByteBuf compressByteBuf;

        public CompressValueItr(ByteBuf compressByteBuf) {
            this.compressByteBuf = compressByteBuf.copy();
        }

        public boolean hasNext() {
            if (!compressByteBuf.isReadable()){
                return false;
            }
            if (compressByteBuf.readerIndex()==compressByteBuf.capacity()-1 && bitIndex>lastBitIndex){
                return false;
            }
            return true;
        }

        @SuppressWarnings("unchecked")
        public StringBuffer next() {
            ifThrow(!hasNext(),()->new ConcurrentModificationException());
            if (root instanceof HuffmanLeaf){
                bitIndex = getByteRemainder(bitIndex+1);
                if (compressByteBuf.isReadable()){
                    compressByteBuf.readByte();
                }
                if (bitIndex>0){
                    compressByteBuf.readerIndex(compressByteBuf.readerIndex()-1);
                }
                return new StringBuffer("0");
            }
            return resolveHuffmanLeaf(new ResolveHuffmanLeaf(root, bitIndex, new StringBuffer()));
        }

        private class ResolveHuffmanLeaf<T>{
            HuffmanNode<T> huffmanNode;
            byte readByte;
            int nowBitIndex;
            private StringBuffer stringBuffer;
            private ResolveHuffmanLeaf(HuffmanNode<T> huffmanNode, byte readByte, int nowBitIndex) {
                this.huffmanNode = huffmanNode;
                this.readByte = readByte;
                this.nowBitIndex = nowBitIndex;
            }

            public ResolveHuffmanLeaf(HuffmanNode<T> huffmanNode, int nowBitIndex, StringBuffer stringBuffer) {
                this.huffmanNode = huffmanNode;
                this.nowBitIndex = nowBitIndex;
                this.stringBuffer = stringBuffer;
            }
        }

        private byte readNextByte(){
            return compressByteBuf.readByte();
        }

        private StringBuffer resolveHuffmanLeaf(ResolveHuffmanLeaf<T> resolveHuffmanLeaf){
            if (resolveHuffmanLeaf.huffmanNode instanceof HuffmanLeaf){
                /**
                 * 如果不是这个byte的最后一位则ByteBuf的readIndex回退一位
                 */

                bitIndex = resolveHuffmanLeaf.nowBitIndex;
                /**
                 * 如果到了最后一个
                 */
                if (bitIndex==0 && !compressByteBuf.isReadable() && lastBitIndex==7){

                }else {
                    compressByteBuf.readerIndex(compressByteBuf.readerIndex() - 1);
                }
                return resolveHuffmanLeaf.stringBuffer;
            }
            if (isTrueAtBitIndex(resolveHuffmanLeaf.readByte,resolveHuffmanLeaf.nowBitIndex)){
                resolveHuffmanLeaf.huffmanNode = resolveHuffmanLeaf.huffmanNode.right;
                resolveHuffmanLeaf.stringBuffer.append("1");
            }else {
                resolveHuffmanLeaf.huffmanNode = resolveHuffmanLeaf.huffmanNode.left;
                resolveHuffmanLeaf.stringBuffer.append("0");
            }
            resolveHuffmanLeaf.nowBitIndex = getByteRemainder(resolveHuffmanLeaf.nowBitIndex+1);
            if (resolveHuffmanLeaf.nowBitIndex==0 && compressByteBuf.isReadable()){
                resolveHuffmanLeaf.readByte = readNextByte();
            }
            return resolveHuffmanLeaf(resolveHuffmanLeaf);
        }

        private byte readByte() {
            byte readByte = compressByteBuf.readByte();
            if (bitIndex>0){
                if (hasNext()){
                    readByte = combineBytes(readByte,compressByteBuf.readByte(),bitIndex);
                    /**
                     * 指针回退一位防止下次漏掉拼接的数据
                     */
                    compressByteBuf.readerIndex(compressByteBuf.readerIndex()-1);
                }else {
                    readByte = splitByte(readByte,bitIndex,lastBitIndex);
                    bitIndex = lastBitIndex;
                }
            }
            return readByte;
        }

//        public void remove() {
//            if (lastRet < 0)
//                throw new IllegalStateException();
//            checkForComodification();
//
//            try {
//                ArrayList.this.remove(lastRet);
//                cursor = lastRet;
//                lastRet = -1;
//                expectedModCount = modCount;
//            } catch (IndexOutOfBoundsException ex) {
//                throw new ConcurrentModificationException();
//            }
//        }


        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super StringBuffer> consumer) {
            Objects.requireNonNull(consumer);
            if (!hasNext()){
                return;
            }
            consumer.accept(next());
        }
    }

    protected void buildAllNode() {
        assert huffmanTrees.size() >= 1;
        int deep = getDeep();
        while (huffmanTrees.size() >= 2) {
            huffmanTrees.offer(new HuffmanNode(huffmanTrees.poll().setDeep(deep), huffmanTrees.poll().setDeep(deep)));
            deep=deep-1;
        }
        root = huffmanTrees.poll().setDeep(deep);
    }

    protected List<HuffmanNode<T>> getHuffmanTreeListByDeep(int deep){
        ifThrow(deep>getDeep(),()->new ArrayIndexOutOfBoundsException(deep));
        List<HuffmanNode<T>> huffmanTreeList = ImmutableList.of(root);
        for (int i = 0; i < deep+1; i++) {
            if (i==deep){
                return huffmanTreeList;
            }
            List<HuffmanNode<T>> huffmanNodeList = filterHuffmanNodes(huffmanTreeList);
            huffmanTreeList = mergeList(huffmanNodeList,x-> ImmutableList.of(x.left,x.right));
        }
        return ImmutableList.of();
    }

    protected List<HuffmanNode<T>> filterHuffmanNodes(List<HuffmanNode<T>> huffmanTreeList) {
        return filterList(huffmanTreeList, x -> !(x instanceof HuffmanLeaf));
    }
//    protected List<HuffmanLeaf<T>> filterHuffmanLeafs(List<HuffmanNode<T>> huffmanTreeList) {
//        return huffmanTreeList.stream().filter(x->x instanceof HuffmanLeaf).map(x->(HuffmanLeaf)x).collect(Collectors.toList());
//    }

    @Override
    public List<HuffmanNode<T>> getAllHuffmanTreeList(){
        List<HuffmanNode<T>> huffmanTreeList = ImmutableList.of(root);
        List<HuffmanNode<T>> result = new ArrayList<>();
        while (!huffmanTreeList.isEmpty()){
            result.addAll(filterList(huffmanTreeList,x-> x instanceof HuffmanLeaf));
            List<HuffmanNode<T>> huffmanNodeList = filterHuffmanNodes(huffmanTreeList);
            result.addAll(huffmanNodeList);
            huffmanTreeList = mergeList(huffmanNodeList,x-> ImmutableList.of(x.left,x.right));
        }
        return result;
    }
    protected List<HuffmanNode<T>> getHuffmanTreeListAboveDeep(int deep){
        ifThrow(deep>getDeep(),()->new ArrayIndexOutOfBoundsException(deep));
        List<HuffmanNode<T>> huffmanTreeList = ImmutableList.of(root);
        List<HuffmanNode<T>> result = new ArrayList<>();
        for (int i = 0; i < deep+1; i++) {
            result.addAll(huffmanTreeList);
            if (i==deep){
                return result;
            }
            List<HuffmanNode<T>> huffmanNodeList = filterHuffmanNodes(huffmanTreeList);
            huffmanTreeList = mergeList(huffmanNodeList,x-> ImmutableList.of(x.left,x.right));
        }
        return result;
    }

    protected HuffmanLeaf<T> getHuffmanLeaf(T value){
        String code = Optional.ofNullable(compressMappingResult.get(value)).orElseThrow(()->new NullPointerException("can niot find this value"));
        char[] chars = code.toCharArray();
        HuffmanNode<T> huffmanTree = root;
        for (int i = 0; i < chars.length; i++) {
            final int index=i;
            ifThrow(!(huffmanTree instanceof HuffmanNode),()->new ClassCastException("the tree data is error,value:"+value+",compressed index:"+index+",compressed data:"+code));
            HuffmanNode<T> huffmanNode = (HuffmanNode)huffmanTree;
            if (chars[i]==48){
                huffmanTree = huffmanNode.left;
            }
            if (chars[i]==49){
                huffmanTree = huffmanNode.right;
            }
            if (i==chars.length-1){
                ifThrow(!(huffmanTree instanceof HuffmanNode),()->new ClassCastException("the tree data is error,value:"+value+",compressed index:"+index+",compressed data:"+code));
                return (HuffmanLeaf<T>)huffmanTree;
            }
        }
        throw new NullPointerException("can not find data,value:"+value);
    }


    /**
     * 数学归纳法得证哈夫曼树的高度等于叶节点数-1，但是其层数跟叶节点数相同
     * @return
     */
    protected int getDeep(){
        return valueFrequency.size()-1;
    }

    protected void buildCompressMappingResult(HuffmanNode<T> tree, StringBuffer prefix, Map<T, String> result) {
        assert tree != null;
        List<HuffmanNode<T>> allHuffmanTreeList = getAllHuffmanTreeList();
        if (allHuffmanTreeList.size()==1 && allHuffmanTreeList.get(0) instanceof HuffmanLeaf){
            T value = ((HuffmanLeaf<T>) allHuffmanTreeList.get(0)).value;
            result.put(value,"0");
            return;
        }
        if (tree instanceof HuffmanLeaf) {
            HuffmanLeaf<T> leaf = (HuffmanLeaf) tree;
            result.put(leaf.value, prefix.toString());
        } else if (!(tree instanceof HuffmanLeaf)) {
            HuffmanNode node = (HuffmanNode) tree;
            prefix.append('0');
            buildCompressMappingResult(node.left, prefix, result);
            prefix.deleteCharAt(prefix.length() - 1);
            prefix.append('1');
            buildCompressMappingResult(node.right, prefix, result);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    protected void calculateValueFrequency() {
        this.valueFrequency = this.valueList.stream().collect(Collectors.groupingBy(x -> x, Collectors.counting()));
    }

    protected void buildAllLeaf(){
        this.valueFrequency.keySet().stream().map(x->new HuffmanLeaf(valueFrequency.get(x), x)).forEach(huffmanTrees::offer);
    }



    @Override
    public abstract void addValue(T value);

    @Override
    public abstract void deleteValue(T node);

    @Override
    public abstract void addValueList(List<T> valueList);

    @Override
    public abstract void deleteValueList(List<T> valueList);

    @Override
    public abstract void addHuffmanTree(HuffmanTree<T> huffmanTree);

    @Override
    public List<T> getValueList(){
        return valueList;
    }

}
